/**
 * ˳��������ڴ��Ͽ���һƬ�����Ŀռ�
 */
 
#include<iostream>
#define InitSize 10

using namespace std;
// ��̬���� 
//typedef struct{
//	int data[MaxSize];
//	int length;		
//}SqList;
// ��̬���� 
typedef struct{
	int *data;	// ָʾ��̬���������ָ�� 
	int MaxSize,Length;	// �������������͵�ǰ���� 
}SqList;

// ��ϰ��1
bool test1(SqList &L,int &e)
{
	if(L.Length == 0){
		cout<<"����"<<endl;
		return false;
	}
	else
	{
		e = L.data[0];
		int min = 0;// λ�� 
		for(int i=1;i<L.Length;i++){
			if(L.data[i]<e){// ��e��˳�������Ƚ� 
				e = L.data[i];
				min = i;
			}
		}
		L.data[min] = L.data[L.Length-1];
		L.Length--;// �ǵ�ɾ���ڵ� 
	}
	return true;
} 
// ��ϰ��2
void test2(SqList &L)
{
	int temp = 0;// �������� 
	for(int i=0;i<(L.Length/2);i++){
		temp = L.data[(L.Length-1-i)];
		L.data[(L.Length-1-i)] = L.data[i];
		L.data[i] = temp;
	}
} 

//3
// ��1 ͳ�Ʋ���x�����ж��ٸ� 
void test3_1(SqList &L, int x)
{
	int k = 0; 
	for(int i=0;i<L.Length;i++){
		if(L.data[i]!=x){
			L.data[k] = L.data[i];
			k++;// Ҫ����if 
		}

	}
	L.Length = k;
} 
// ͳ�Ƶ���x���� 
void test3_2(SqList &L, int x)
{
	int k = 0, i = 0;
	while(i<L.Length){
		if(L.data[i]==x){
			k++;
		}
		else
		{
			L.data[i-k] = L.data[i];
		}
		i++;
	}
	L.Length = L.Length-k;
} 
// 9
void test9(SqList &L,int x)
{
	if(x>L.data[(L.Length/2)]){
		int temp = 0;
		for(int i=(L.Length/2);i<L.Length;i++){
			if(x==L.data[i]){
				temp = L.data[i+1];
				L.data[i+1] = L.data[i];
				L.data[i] = temp;
			}
			else
			{
				while(x>L.data[i]&&x<L.data[i+1]&&i<=L.Length){
					i++;
				}
			}
		}
	}
}
void test4(SqList &L,int x)
{
	int n = L.Length;
	int low = 0,high = L.Length -1,mid;
	while(low<=high){
		mid = (low+high)/2;
		if(L.data[mid] == x){
			break;
		}
		else if(L.data[mid]<x){
			low = mid +1;
		}
		else
		{
			high = mid -1;
		}
	}int temp = 0;
	if(L.data[mid] == x && mid != n-1){
		temp = L.data[mid];
		L.data[mid] = L.data[mid+1];
		L.data[mid+1] = temp;
	}
	int i ;
	if(low > high){
		for(i=n-1;i>high;i--){
			L.data[i+1] = L.data[i];
		}
		L.data[i+1] = x;
	}
	
}
void InitList(SqList &L)
{
	// c�ķ���ռ�����ǣ�; 
	L.data = (int*)malloc(sizeof(int)*InitSize);
	L.Length = 0;
	L.MaxSize = InitSize;
} 

// ����˳�����Ҫ���λ�ú�ֵ 
bool InsertList(SqList &L,int i, int e)
{
	if(i<1||i>L.MaxSize)	// �ж�i�Ƿ�Ϸ� 
	{
		return false;
	} 
	if(L.Length >= L.MaxSize)
	{
//		L.data = new int(InitSize)
		return false;
	} 
	for(int j = L.Length;j >= i;j--){
		L.data[j] = L.data[j-1]; // ��j-1��ֵ����j 
		/*��Ϊ˳����Ǵ�0��ʼ�� 
		*/
	}
	L.data[i-1] = e;
	L.Length++;
	return true;
}

// ��ֵ���ҷ�������λ�� 
int LocateElem(SqList L,int e)
{
	for(int i=0;i<=L.Length-1;i++){
		if(L.data[i] == e){
			return i+1;
		}
	}
	return 0;
}

bool Del_List(SqList &L,int i, int &e)
{
	if(i<1||i>L.MaxSize)	// �ж�i�Ƿ�Ϸ� 
	{
		return false;
	} 
	if(L.Length == 0){
		return false;
	}
	e = L.data[i-1];
//	for(int j = L.Length-1;j>=i;j--){
//		L.data[j-1] = L.data[j];
//	}
	/*�����Ǵ���ģ��൱�ڰ�˳��������һ��ֵ
	*һ·����ǰ���ֵ��i-1�� λ�� 
	*/
	for(int j = i;j<L.Length-1;i++){
		L.data[j-1] = L.data[j];
	}	
	L.Length--;
	return true; 
}
void ShowList(SqList L)
{
	for(int i=0;i<=L.Length-1;i++){
		cout<<L.data[i]<<"\t";
	}
}
int main()
{
	SqList L;
//	int e = 0;
	InitList(L);
	InsertList(L,1,34);
	InsertList(L,2,43);
	InsertList(L,3,78);
	InsertList(L,4,88);
	InsertList(L,5,90);
	ShowList(L);
	test4(L,56);
	cout<<"��������";
	ShowList(L);
	return 0;
} 
